import java.util.Arrays;

/**
 * @ClassName: Algorithm-and-Data-Structure
 * @Description:
 * @Author: zhouhong
 * @Create: 2021-04-06 23:46
 **/

public class MergeSort {
    private MergeSort(){}

    // 自定向上归并
    public static <E extends Comparable<E>> void  sort(E[] arr){
        sort(arr, 0, arr.length - 1);
    }
    private static <E extends Comparable<E>> void sort(E[] arr, int l, int r){
        if (l >= r){
            return;
        }else {
            int mid = l + (r - l) / 2;
            sort(arr, l, mid);
            sort(arr, mid + 1, r);
            if (arr[mid].compareTo(arr[mid + 1]) > 0){
                merge(arr, l, mid, r);
            }
        }
    }


    // 合并两个有序的区间， arr[l, mid] 和 arr[mid + 1, r]
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r){
        // 拷贝一份新的数组
        // E[] temp = Arrays.copyOfRange(arr, l, r + 1);
        E[] temp = Arrays.copyOf(arr, arr.length);
        int i = l, j = mid + 1;
        // 每轮循环为 arr[k]赋值
        for (int k = l; k <= r; k++) {
            if (i > mid){
                // 因为temp是从 0 开始的的，temp[0] -- arr[l] 会有一个 l 的偏移量
                arr[k] = temp[j];
                j ++;
            }else if (j > r){
                arr[k] = temp[i];
                i ++;
            }else if (temp[i].compareTo(temp[j]) <= 0){
                arr[k] = temp[i];
                i ++;
            }else {
                arr[k] = temp[j];
                j ++;
            }
        }
    }

    public static void main(String[] args) {

        //int n = 100000;
        //Integer[] arr =  ArrayGenerator.generatorRandomArray(n, n);
        //SortingHelper.sortTest("mergeSort", arr);
        Integer[] arr = {1,23,3,43,5,2,65,76,2,34,56,2,7,88,875};
        sort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
